from sys import exit
from random import random
from sys import stdin
from time import time
import os

# Psyco doesn't work on PowerPC
#import psyco
#psyco.full()

T = 'T'
nil = []

# Compiler mappings
# (will be created through scanning a file then scanning any modules)
mappings = {"print":"print_compile",
            "return":"return_compile",
            "length":"length_compile",
            "fn":"function_compile"}

def open_cpp_file (filename):
    file = open (filename + ".cpp", "w")
    file.write ("#include <stdio.h>\n")
    file.write ("#include <stdlib.h>\n")
    file.write ("#include <string.h>\n")
    file.write ("#include <iostream>\n\n")
    file.write ("using namespace std;\n\n");
    file.write ("int\nmain (int argc, char *argv[])\n{\n");
    return file

def close_cpp_file (filename, file, return_code):
    if file == None:
        file = open (filename + ".cpp", "a")
    file.write ("  return " + str(return_code) + ";")
    file.write ("\n}\n")
    file.close ()

def kill_cpp_file (filename, file):
    if file:
        file.close ()
    filename = filename + ".cpp"
    os.remove (filename)

def return_compile (args):
    if args:
        return "return " + str(args) + ";\n"
    return "return 0;\n"

def length_compile (args):
    if args and len(args) == 1:
        return len (args[0])
    return ""

def print_compile (args):
    format = ""
    output = ""
    for i in range (0, len (args)):
        if type(args[i]) == str:
            format += "%s"
        elif type(args[i]) == int:
            format += "%i"
        elif type(args[i]) == float:
            format += "%f"
    for var in range (0, len (args)):
        output += ", "
        if type(args[var]) == str:
            output += "\"" + args[i] + "\""
        else:
            output += str(args[i])          
    return "printf (\"" + format + "\"" + output + ");\n"

# (fn name (args) (blah) (blah) return-val)
def function_compile (args):
    output = ""
    # We're going to have to code-walk the list to find
    # any (return) calls and check to make sure the
    # types are the same

    # If the types are different, the function will
    # return a dObject pointer

    # As a last resort, we check the final value's type
    print "args: " + str(args)
    if type(args[-1]) == list and len(args[-1]) > 0:
        args[-1] = eval_ (args[-1])
    if type(args[-1]) == list:
        output += "dList *"
    elif type(args[-1]) == str:
        output += "string"
    elif type(args[-1]) == int:
        # Also need to check if the big-num library is being used 
        output += "int"
    elif type (args[-1]) == float:
        # Again, check for big-num library
        output += "double"

    output += "\n" + args[0] + "\n{\n"

    for i in range (2, len (args)-1):
        if len(args[i]) > 0:
            output += str(compile (args[i]))
    if type(args[-1]) == list:
        return output + "return " + compile (args[-1]) + ";\n}\n"
    return output + return_compile (args[-1]) + "}\n"

def compile (expn):
    return eval (mappings[expn[0]] + "(" + str(expn[1:]) + ")")

def compileToFile (filename, file, expn):
    if file == None:
        file = open (filename + ".cpp", "a")
    print "Compiling expression: " + str(expn)
    if mappings.has_key (expn[0]):
        file.write (compile (expn))
    elif expn[0] == "quit":
        if len(expn) == 2:
            close_cpp_file (filename, file, int(expn[1]))
            exit (expn[1])
        else:
            close_cpp_file (filename, file, 0)
            exit (0)

def parse(expn):
    if (expn.count('(') == 0) and (expn.count(' ') == 0):
        if expn[0] == "'":
            return ['quote', parse(expn[1:])]
        if nump(expn):
            return float(expn)
        else:
            return expn
    elif expn[0] == "'":
        return ['quote', parse(expn[1:])]
    output = []
    subp = 0
    strp = 0
    strexpn = ""
    subexpn = ""
    count = 0
    expn = expn[1:-1]
    expn = expn.split(' ')
    q = 0
    for token in expn:
        if token == '':
            continue
        if strp:
            if token[-1] == '"':
               strexpn += token
               output += [strexpn]
               strp = 0
               continue
        elif token[0] == '"':
            strp = 1
            strexpn += token
            continue
        ocount = token.count('(')
        ccount = token.count(')')
        count += ocount - ccount
        if (ocount == ccount) and (ocount > 0):
            subp = 1
        if token[0] == "'":
            q = 1
        else:
            q = 0
        if subp:
            if count == 0:
                subp = 0
                subexpn += token
                output.append(parse(subexpn))
                if q:
                    q = 0
                subexpn = ""
            else:
                subexpn += token + ' '
        else:
            if count > 0:
                subp = 1
                subexpn += token + ' '
            else:
                if q:
                    output.append(['quote', parse(token[1:])])
                    q = 0
                elif nump(token):
                    output.append(float(token))
                else:
                    output.append(token)
    return output

def add(args):
    return sum(args)

def subtract(args):
    if len(args) > 2:
        val = args[0] - args[1]
        return subtract([val] + args[2:])
    else:
        return args[0] - args[1]

def multiply(args):
    prod = 1
    for i in args:
        prod *= i
    return prod

def divide(args):
    if len(args) > 2:
        val = args[0] / float(args[1])
        return divide([val] + args[2:])
    else:
        return args[0] / float(args[1])

def eq(args):
    if args[0] == args[1]:
        return T
    else:
        return nil

def cons(args):
    return [args[0]] + args[1]    

def car(args):
    try:
        return args[0][0]
    except:
        return nil
    
def cdr(args):
    try:
        return args[0][1:]
    except:
        return nil

def list_(args):
    return args

def and_(args):
    for i in args:
        if i == nil:
            return nil
    return T

def or_(args):
    for i in args:
        if i != nil:
            return i
    return nil

def not_(args):
    if args[0] == nil:
        return T
    else:
        return nil

def greater(args):
    if args[0] > args[1]:
        return T
    else:
        return nil

def less(args):
    if args[0] < args[1]:
        return T
    else:
        return nil

def greatereq(args):
    if args[0] >= args[1]:
        return T
    else:
        return nil

def lesseq(args):
    if args[0] <= args[1]:
        return T
    else:
        return nil

def random_(args):
    return args[0] * random()

def mod(args):
    return args[0] % args[1]

def if_(args, env):
    if evaluate(args[0], env) != nil:
        return evaluate(args[1], env)
    else:
        if len(args) > 2:
            return evaluate(args[2], env)
        else:
            return nil

def while_(test, body, env):
    value = nil
    while not (evaluate(test, env) == nil):
        for i in body:
            value = evaluate(i, env)
    return value

def cond(args, env):
    for pair in args:
        if evaluate(pair[0], env) != nil:
          return evaluate(pair[1], env)
    return nil

def replace(pairs, tree):
    result = []
    for node in tree:
        if type(node) == list:
            result.append(replace(pairs, node))
        else:
            found = False
            for name, value in pairs:
                if node == name:
                    result.append(value)
                    found = True
            if not found:
                result.append(node)
    return result
                    


def eval_(args):
    return evaluate(args[0], args[1])

class lambda_:
    def __init__(self, args, expns, env):
        self.rest = 0
        self.genv = env
        self.lenv = []
        self.dargs = [a for a in args if a.__class__ == list]
        self.dargs = [(a[0], evaluate(a[1], env)) for a in self.dargs]                
        self.args = args[:(len(args) - len(self.dargs))]
        self.expns = expns
    def __call__(self, args):
        argenv = []
        if len(args) < len(self.args):
            print "Insufficient arguments"
            return nil
        elif len(args) > (len(self.args) + len(self.dargs)):
            print "Too many arguments"
            return nil
        elif len(args) == len(self.args):
            argenv += zip(self.args, args) + self.dargs
        else:
            argenv = zip(self.args, args[:len(self.args)])
            dargs = args[len(self.args):]
            for i in range(len(dargs)):
                argenv.insert(0, (self.dargs[i][0], dargs[i]))
            if len(dargs) < len(self.dargs):
                argenv = self.dargs[len(dargs):]
        value = nil
        currenv = argenv + self.lenv + self.genv
        assigns = 0
        currsize = len(currenv)
        for expn in self.expns:
            value = evaluate(expn, currenv)
            if len(currenv) > currsize:
                assigns += 1
                currsize += 1
        self.lenv = currenv[:assigns] + self.lenv
        return value


class macro_:
    def __init__(self, args, expns, env):
        self.rest = 0
        self.genv = env
        self.dargs = [a for a in args if a.__class__ == list]
        self.dargs = [(a[0], evaluate(a[1], env)) for a in self.dargs]                
        self.args = args[:(len(args) - len(self.dargs))]
        self.expns = expns
    def __call__(self, args):
        argenv = []
        if len(args) < len(self.args):
            print "Insufficient arguments"
            return nil
        elif len(args) > (len(self.args) + len(self.dargs)):
            print "Too many arguments"
            return nil
        elif len(args) == len(self.args):
            argenv += zip(self.args, args) + self.dargs
        else:
            argenv = zip(self.args, args[:len(self.args)])
            dargs = args[len(self.args):]
            for i in range(len(dargs)):
                argenv.insert(0, (self.dargs[i][0], dargs[i]))
            if len(dargs) < len(self.dargs):
                argenv = self.dargs[len(dargs):]
        value = nil
        currenv = argenv + self.genv
        assigns = 0
        currsize = len(currenv)
        for expn in self.expns:
            print 'Expression: ' + format(expn)
            expn = replace(argenv, expn)
            print 'Expanded  : ' + format(expn)
            value = evaluate(expn, currenv)
            if len(currenv) > currsize:
                assigns += 1
                currsize += 1
        for pair in currenv[:assigns]:
            self.genv.insert(0, pair)
        return value

    

def nump(token):
    if token[0] == '-':
        if len(token) > 1:
            token = token[1:]
        else:
            return False
    for c in token:
        if c not in ['1', '2', '3', '4', '5', '6', '7', '8', '9', '0', '.', '-']:
            return False
    return True

def nump_(args):
    if args[0].__class__ == float:
        return T
    else:
        return nil

def symbolp(args):
    if args[0].__class__ == str:
        return T
    else:
        return nil

def listp(args):
    if args[0].__class__ == list:
        return T
    else:
        return nil

def lambdap(args):
    if args[0].__class__ == lambda_:
        return T
    else:
        return nil

def lookup(args):
    symbol = args[0]
    env = args[1]
    for pair in env:
        if pair[0] == symbol:
            return pair[1]
    print 'Unknown value ', symbol
    return nil

def print_(args):
    for i in args:
        print format(i)
    return T

def assoc(args):
    symbol = args[0]
    value = args[1]
    env = args[2]
##    for i in range(len(env)):
##        if env[i][0] == symbol:
##            env[i][1] = value
##            return value
    env.insert(0, [symbol, value])
    return value

def length(args):
    arg = args[0]
    if not(listp([arg])):
        return nil
    return len(arg)

def time_(args):
    return time()

def quit_(args):
    import sys
    sys.exit('plz')

def append(args):
    result = []
    for i in args:
        result += i
    return result





def evaluate(expn, env):
    if expn == T:
        return T
    elif (expn == 'nil') or (expn == nil):
        return nil
    elif expn.__class__ == float:
        return expn
    elif expn[0] == 'quote':
        return expn[1]
    elif expn[0] == 'lambda':
        return lambda_(expn[1], expn[2:], env)
    elif expn[0] == 'macro':
        return macro_(expn[1], expn[2:], env)
    elif expn[0] == 'function':
        fn = lambda_(expn[2], expn[3:], env)
        name = expn[1]
        assoc((name, fn, env))
        return fn
    elif expn[0].__class__ == list:
        return assoc((evaluate(expn[0], env), evaluate(expn[1], env), env))
    elif expn[0] == 'let':
        return assoc((evaluate(expn[1], env), evaluate(expn[2], env), env))
    elif expn[0] == 'if':
        return if_(expn[1:], env)
    elif expn[0] == 'cond':
        return cond(expn[1:], env)
    elif expn[0] == 'while':
        return while_(expn[1], expn[2:], env)
    elif expn.__class__ == str:
        return lookup((expn, env))
    elif expn.__class__ != list:
        print "Can't evaluate ", expn
        return nil
    else:
        fn = evaluate(expn[0], env)
        if fn == nil:
            return "Unknown function %s" % expn[0]
        elif fn.__class__ == add.__class__:
            args = [evaluate(i, env) for i in expn[1:]]            
            return apply(fn, [args])
        elif fn.__class__ == macro_([], [], []).__class__:
            args = expn[1:]
            return fn(args)
        else:
            args = [evaluate(i, env) for i in expn[1:]]                        
            return fn(args)

def format(expn):
    if (expn.__class__ == str):
        expn = expn.replace('()', 'nil')
        return expn
    if (expn.__class__ == float):
        return expn
    elif expn.__class__ == list:
        out = "("
        for i in expn:
            if i.__class__ == list:
                out += format(i) + ' '
            else:
                out += str(i) + ' '
        if len(out) > 1:
            out = out[:-1] + ")"
        else:
            out += ")"
        out = out.replace('[', '(')
        out = out.replace(']', ')')
        out = out.replace('()', 'nil')
        return out
    else:
        return expn

def getenv(env):
    f = [i for i in env if i[0] == 'env']
    return f[0][1]


env = [
    ['+', add],
    ['-', subtract],
    ['*', multiply],
    ['/', divide],
    ['eq', eq],
    ['cons', cons],
    ['car', car],
    ['cdr', cdr],
    ['first', car],
    ['rest', cdr],
    ['list', list_],
    ['and', and_],
    ['or', or_],
    ['not', not_],
    ['>', greater],
    ['<', less],
    ['>=', greatereq],
    ['<=', lesseq],
    ['mod', mod],
    ['eval', eval_],
    ['nump', nump_],
    ['symbolp', symbolp],
    ['lambdap', lambdap],
    ['lookup', lookup],
    ['assoc', assoc],
    ['listp', listp],
    ['length', length],
    ['time', time_],
    ['random', random_],
    ['quit', quit_],
    ['append', append],
    ['print', print_]]

env.insert(0, ('env', env))
file = open_cpp_file ("test")
def repl(env):
    while 1:
        print "<DLisp>>",
        count = 0
        line = ""
        while 1:
            text = stdin.readline()
            openb = text.count('(')
            closeb = text.count(')')
            count += openb - closeb
            line += text[:-1] + ' '
            if count <= 0:
                break
        compileToFile ("test", file, parse(line[:-1]))
        #try:
            #print format(evaluate(parse(line[:-1]), env))
        #except:
            #print "Unhandled Error"


def empty(text):
    for c in text:
        if c != ' ':
            return False
    return True

def load(body, env):
    count = 0
    expn = ""
    for token in body.split('\n'):
        if not empty(token):
            count += token.count('(') - token.count(')')
            expn += token
            if count == 0:
                print evaluate(parse(expn), env)
                expn = ""
    
utilities = """

('isprime
  (lambda (guess primes)
    (if primes
     (if (eq (mod guess (first primes)) 0)
       nil
       (isprime guess (rest primes)))
      T)))

('nprimes
  (lambda (n (guess 3) (primes '(2)))
    (if (> n 1)
     (if (isprime guess primes)
      (nprimes (- n 1) (+ guess 1) (cons guess primes))
      (nprimes n (+ guess 1) primes))
      primes)))


('clock
  (lambda (expn)
    ('start (time))
    (eval expn env)
    (- (time) start)))

('map
  (lambda (fn list (collected nil))
   (if list
    (map fn (rest list) (cons (fn (first list)) collected))
    (reverse collected))))

('reduce
  (lambda (fn list (result nil))
   (if list
     (if result
       (reduce fn (rest list) (fn (first list) result))
       (reduce fn (rest (rest list)) (fn (first list) (first (rest list)))))
      result)))

('reverse
  (lambda (list (collected nil))
   (if list
    (reverse (rest list) (cons (first list) collected))
    collected)))


"""

load(utilities, env)

if __name__ == '__main__':
    repl(env)
